package algorithms.a04heap;

import algorithms.utis.AlgorithmsUtis;
import algorithms.utis.SortTestHelper;
import com.google.common.base.Preconditions;
import org.apache.commons.lang3.RandomUtils;

/**
 * 最大堆
 * 实质是一个完全二叉树
 *
 * @author 王昊然
 * @create 2018-02-08 16:19
 **/
public class MaxHeap<Item extends Comparable> {

    private int capacity;
    private int count = 0;//
    private Item[] data;

    public MaxHeap(int capacity) {
        this.capacity = capacity;
        data = (Item[]) new Comparable[capacity + 1];//从下标1开始，第一个位置空出来，以满足child/2 = parent的索引性质
    }

    public MaxHeap(Comparable[] arr) {
        this.capacity = arr.length;
        data = (Item[]) new Comparable[capacity + 1];//从下标1开始，第一个位置空出来，以满足child/2 = parent的索引性质

        for(int i = 1; i<=capacity; i++){
            data[i] = (Item) arr[i-1];
        }
        this.count = capacity;

        //heapify
        for(int i = count/2; i>0; i--){
            shiftDown(i);
        }
    }


    public void insert(Item item) {

        Preconditions.checkArgument(capacity >= count, "堆数组的容量已不足，无法插入新元素！");

        data[++count] = item;

        this.shiftUp(count);
    }

    public Item extractMax() {

        Item max = data[1];

        AlgorithmsUtis.swap(data, 1, count);
        count--;

        this.shiftDown(1);

        return max;
    }

    private void shiftUp(int i) {

        Item e = data[i];

        while (i > 1 && data[i / 2].compareTo(e) < 0) {
            data[i] = data[i/2];
            i /= 2;
        }

        data[i] = e;
    }

    private void shiftDown(int i) {

        Item e = data[i];

        int c = 2 * i;//要和i比较的子节点下标，默认是左子节点

        while (c <= count) {

            int right = c + 1;
            //c取左右子节点最大值下标
            if (right <= count && data[c].compareTo(data[right]) < 0) {
                c = right;
            }

            //只有在交换过的情况下进入下一循环，否则break
            if (e.compareTo(data[c]) < 0) {
                data[i] = data[c];
                i = c;
                c = 2*i;

            } else {
                break;
            }
        }

        data[i] = e;


    } public Item[] getData() {
        return data;
    }

    public boolean isEmpty() {
        return count == 0;
    }

    public int size() {
        return count;
    }




    public static void main(String[] args) {
        MaxHeap<Integer> heap = new MaxHeap<>(10);
        testInsert(heap);
        testExtractMax(heap);






    }

    private static void testInsert(MaxHeap heap) {

        int count = heap.getData().length - 1;
        while (count > 0) {
            heap.insert(RandomUtils.nextInt(1, 100));
            count--;
        }
        System.out.println(SortTestHelper.printArray(heap.getData()));
    }

    private static void testExtractMax(MaxHeap heap) {

        while (!heap.isEmpty()) {
            System.out.println(heap.extractMax());
        }

    }
}

